# 5 中等：最长回文子串

def longestPalindrome(s):
    length = len(s)
    # 单个字符是回文串
    if length < 2:
        return s

    # 动态规划
    # 初始化动态数组
    dp = [[False] * length for _ in range(length)]
    for i in range(length):
        dp[i][i] = True

    maxm, begin = 1, 0
    for l in range(2, length + 1):
        for i in range(0, length - l + 1):
            # 右边界
            j = i + l - 1
            if s[i] != s[j]:
                dp[i][j] = False
            else:
                if l < 4:
                    dp[i][j] = True
                else:
                    dp[i][j] = dp[i+1][j-1]
                if dp[i][j] and l > maxm:
                    maxm = l
                    begin = i
    return s[begin:begin+maxm]


print(longestPalindrome('b'))
